package _18_剑指OfferII;

public class _094_剑指OfferII最少回文分割 {

    public static void main(String[] args) {

        _094_剑指OfferII最少回文分割 v = new _094_剑指OfferII最少回文分割();

        String str = "aab";
        System.out.println(v.minCut(str));

    }

    // 中心扩展寻找回文
    public int minCut(String s) {
        int len = s.length();
        int[] dp = new int[len + 1];
        // 初始化dp数据
        for (int i = 0; i <= len; i++) {
            dp[i] = i - 1;
        }

        for (int i = 1; i <= len; i++) {
            set(i - 1, i - 1, s, dp);
            set(i - 1, i, s, dp);
        }
        return dp[len];
    }

    public void set(int i, int j, String str, int[] dp) {
        int len = str.length();
        while (i >= 0 && j < len && str.charAt(i) == str.charAt(j)) {
            dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1);
            i--;
            j++;
        }
    }

    // 动态规划，寻找最小分割子回文
    public int minCut1(String s) {
        int len = s.length();
        // 记录dp[i][j] 区间是否为回文串
        boolean[][] isPalindromic = new boolean[len][len];
        for (int i = len - 1; i >= 0; --i) {
            isPalindromic[i][i] = true;
            for (int j = i + 1; j < len; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    isPalindromic[i][j] = j - i <= 2 || isPalindromic[i + 1][j - 1];
                }
            }
        }

        // dp[i] 表示0到i区间能最少能分割多少回文串
        int[] isPalindromicCount = new int[len + 1];
        for (int i = 0; i <= len; i++) {
            isPalindromicCount[i] = i - 1;
        }
        for (int i = 1; i <= len; ++i) {
            // 遍历寻找最小分割
            for (int j = 1; j <= i; ++j) {
                if (isPalindromic[j - 1][i - 1]) {
                    isPalindromicCount[i] = Math.min(isPalindromicCount[i], isPalindromicCount[j - 1] + 1);
                }
            }
        }

        return isPalindromicCount[len];
    }

}
